package com.zhaofan.other;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

//用堆栈先将数据放入，如果当前值<上一个值，则上一个值为峰值
//直接用二分查找找最大值
public class No162 {

    @Test
    public void test() {
        int[] nums = {1, 2, 1, 3, 5, 6, 4};
        System.out.println(findPeakElement2(nums));
    }


    public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int min = 0, max = nums.length - 1;
        while (min < max) {
            int mid = min + (max - min) / 2;
            if (nums[mid] < nums[mid + 1]) {
                min = mid + 1;
            } else {
                max = mid;
            }
        }
        return nums[max];
    }

    public int findPeakElement2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int min = 0, max = nums.length - 1;
        while (min < max) {
            int mid = min + (max - min) / 2;
            if (nums[mid] < nums[mid - 1]) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }


}
